{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Orderly Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: orderlyQueue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code> 和一个整数 <code>k</code>&nbsp;。你可以从 <code>s</code> 的前 <code>k</code> 个字母中选择一个，并把它加到字符串的末尾。</p>\n",
    "\n",
    "<p>返回 <em>在应用上述步骤的任意数量的移动后，字典上最小的字符串&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"cba\", k = 1\n",
    "<strong>输出：</strong>\"acb\"\n",
    "<strong>解释：</strong>\n",
    "在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。\n",
    "在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"baaca\", k = 3\n",
    "<strong>输出：</strong>\"aaabc\"\n",
    "<strong>解释：\n",
    "</strong>在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。\n",
    "在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k&nbsp;&lt;= S.length&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>s</code>&nbsp;只由小写字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [orderly-queue](https://leetcode.cn/problems/orderly-queue/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [orderly-queue](https://leetcode.cn/problems/orderly-queue/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cba\"\\n1', '\"baaca\"\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>=2:\n",
    "            return ''.join(sorted(c for c in s))\n",
    "        ans=s\n",
    "        # t=deque(s)\n",
    "        # n=len(s)\n",
    "        # for r,x in enumerate(s):\n",
    "        #     t.append(x)\n",
    "        #     t.popleft()\n",
    "        #     k=''.join(t)\n",
    "        #     if k<ans:\n",
    "        #         ans=k\n",
    "        # return ans\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            k=s[i:]+s[:i]\n",
    "            if k<ans:\n",
    "                ans=k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        return min(s[i:] + s[:i] for i in range(len(s))) if k == 1 else ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for i in range(1, len(s)):\n",
    "                temp = s[i:] + s[:i]\n",
    "                ans = min(ans, temp)\n",
    "            return ans\n",
    "        return \"\".join(sorted(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>1:\n",
    "            return \"\".join(sorted(list(s)))\n",
    "        sec=s\n",
    "        n=len(s)\n",
    "        k, i, j = 0, 0, 1\n",
    "        while k < n and i < n and j < n:\n",
    "            if sec[(i + k) % n] == sec[(j + k) % n]:\n",
    "                k += 1\n",
    "            else:\n",
    "                if sec[(i + k) % n] > sec[(j + k) % n]:\n",
    "                    i = i + k + 1\n",
    "                else:\n",
    "                    j = j + k + 1\n",
    "                if i == j:\n",
    "                    i += 1\n",
    "                k = 0\n",
    "        i = min(i, j)\n",
    "        return s[i:]+s[:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        n=len(s)\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for i in range(n):\n",
    "                a = s[i:]+s[:i]\n",
    "                if a<ans:\n",
    "                    ans = a\n",
    "            return ans\n",
    "        else:\n",
    "            ans = list(s)\n",
    "            ans.sort()\n",
    "            return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>1: return ''.join(sorted(s))\n",
    "        return min((s*2)[i:len(s)+i] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            min_str = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                min_str = min(min_str, s)\n",
    "            return min_str\n",
    "        else: return ''.join(sorted(s))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        a = list(s)\n",
    "        if k == 1:\n",
    "            res = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = a.pop(0)\n",
    "                a.append(s)\n",
    "                t = \"\".join(a)\n",
    "                res = min(res, t)\n",
    "            return res\n",
    "        a.sort()\n",
    "        return \"\".join(a)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        return min(s[i:] + s[:i] for i in range(len(s))) if k == 1 else \"\".join(sorted(s))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k > 1:\n",
    "            return ''.join(sorted(s))\n",
    "        n = len(s)\n",
    "        ans=s\n",
    "        s = s+s\n",
    "        for i in range(n):\n",
    "            ans=min(ans,s[i:n+i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        n=len(s)\n",
    "        if k==1:\n",
    "            ans=s\n",
    "            for i in range(n):\n",
    "                a=s[i:]+s[:i]\n",
    "                if a<ans:\n",
    "                    ans=a\n",
    "            return ans\n",
    "        else:\n",
    "            ans=list(s)\n",
    "            ans.sort()\n",
    "            return ''.join(ans)\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(n):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "\n",
    "        if k > 1:\n",
    "            return ''.join(sorted(s))\n",
    "        minn = s\n",
    "        for i in range(len(s)):\n",
    "            minn = min(minn, s[i:] + s[:i])\n",
    "        return minn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, ss: str, k: int) -> str:\n",
    "        s = list(ss)\n",
    "        if k > 1:\n",
    "            s.sort()\n",
    "            return ''.join(s)\n",
    "        return ''.join(min(s[i:] + s[:i] for i in range(len(s))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return \"\".join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k != 1:\n",
    "            return ''.join(sorted(s))\n",
    "        return min(s[i:] + s[:i] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s)):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            result = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                result = min(result, s)\n",
    "            return result\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if len(s) < 2:\n",
    "            return s\n",
    "        if k >= 2:\n",
    "            return ''.join(sorted(s))\n",
    "        else:\n",
    "            return min(s[i:]+s[:i] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if (k >= 2):\n",
    "            return ''.join(sorted(s))\n",
    "        else:\n",
    "            ans = s\n",
    "            for i in range(len(s)):\n",
    "                ans = min(ans, s[i:] + s[:i])\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        res = ''\n",
    "        if k != 1:\n",
    "            return res.join(sorted(s))\n",
    "        res = s\n",
    "        for i in range(len(s)):\n",
    "            s = s[1:] + s[0]\n",
    "            res = min(res, s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>1:\n",
    "            return ''.join(sorted(s))\n",
    "        else:\n",
    "            new_s = s\n",
    "            for i in range(len(s)):\n",
    "                a = s[i:]+s[:i]\n",
    "                if a<new_s:\n",
    "                    new_s = a\n",
    "            return new_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>=2:\n",
    "            return ''.join(sorted(s))\n",
    "        ans=s\n",
    "        # t=deque(s)\n",
    "        # n=len(s)\n",
    "        # for r,x in enumerate(s):\n",
    "        #     t.append(x)\n",
    "        #     t.popleft()\n",
    "        #     k=''.join(t)\n",
    "        #     if k<ans:\n",
    "        #         ans=k\n",
    "        # return ans\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            k=s[i:]+s[:i]\n",
    "            if k<ans:\n",
    "                ans=k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k!=1:\n",
    "            return ''.join(sorted([j for j in s]))\n",
    "        else:\n",
    "            a = s + s \n",
    "            for j in range(len(s)):\n",
    "                tmp = a[j:j + len(s)]\n",
    "                if s>tmp:\n",
    "                    s = tmp \n",
    "            return s \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s)):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s)-1):\n",
    "                s = s[1:]+s[0]\n",
    "                ans = min(ans,s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        n=len(s)\n",
    "        s1=list(s)\n",
    "        s1.sort()\n",
    "        if k==1:\n",
    "            ans=s\n",
    "            for i in range(n):\n",
    "                s=s[1:]+s[0]\n",
    "                ans=min(ans, s)\n",
    "            return ans\n",
    "                \n",
    "        return \"\".join(s1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        s = list(s)\n",
    "        if k > 1:\n",
    "            t = sorted(s)\n",
    "            return ''.join(t)\n",
    "        else:\n",
    "            ans = ''.join(s)\n",
    "            for i in range(1, len(s)):\n",
    "                t = ''.join(s[i:] + s[:i])\n",
    "                ans = min(ans, t)\n",
    "                \n",
    "\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        # k > 1 可以交换任意相邻元素 等于冒泡排序\n",
    "        if k > 1:\n",
    "            return ''.join(sorted(s))\n",
    "\n",
    "        ans = s\n",
    "        for _ in range(len(s)-1):\n",
    "            s = s[1:] + s[0]\n",
    "            ans = min(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>1: return ''.join(sorted(s))\n",
    "        return min((s*2)[i:len(s)+i] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k != 1:\n",
    "            return \"\".join(sorted(list(s)))\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        MOD = pow(26, n-1)\n",
    "        for c in s:\n",
    "            res = res * 26 + (ord(c) & 31) - 1\n",
    "        tempres = res\n",
    "        for c in s:\n",
    "            res %= MOD\n",
    "            res = res*26 + (ord(c) & 31) - 1\n",
    "            tempres = min(tempres, res)\n",
    "        ret = \"\"\n",
    "        for i in range(n):\n",
    "            ret = chr(tempres % 26 + ord('a')) + ret\n",
    "            tempres //= 26\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        \n",
    "        if k>1:\n",
    "            return ''.join(sorted(s))\n",
    "\n",
    "        else:\n",
    "            min_s=s\n",
    "            for i in range(1,len(s)):\n",
    "                \n",
    "                new_s=s[i:]+s[:i]\n",
    "                min_s = min(min_s,new_s)\n",
    "            return min_s            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(s, ans)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k==1:\n",
    "            minv=min(s)\n",
    "            ans=s  \n",
    "            for i,e in enumerate(s):\n",
    "                if e==minv:\n",
    "                    ans=min(ans,s[i:]+s[:i])\n",
    "            return ans\n",
    "        return ''.join(sorted(s))\n",
    "            \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        return min(s[i:] + s[:i] for i in range(len(s))) if k == 1 else \"\".join(sorted(s))\n",
    "        if k >= 2:\n",
    "            return \"\".join(sorted(s))\n",
    "        else:\n",
    "            for i in range(len(s)):\n",
    "                s = s[1:]+s[0] if (s[1:]+s[0]) <= s else s\n",
    "            return s  \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            a = min(s)\n",
    "            c = s\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == a:\n",
    "                    c = min(c,s[i:]+s[:i])\n",
    "            return c\n",
    "        else:\n",
    "            l = sorted(s)\n",
    "            c = ''.join(l)\n",
    "            return c\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        return min(s[i:] + s[:i] for i in range(len(s))) if k == 1 else \"\".join(sorted(s))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        ans = s\n",
    "        if k == 1:\n",
    "            for i in range(len(s)):\n",
    "                temp = s[i:]+s[:i]\n",
    "                if temp<ans:\n",
    "                    ans = temp\n",
    "        else:\n",
    "            ans = ''.join(sorted(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for i in range(1, len(s)):\n",
    "                temp = s[i:] + s[:i]\n",
    "                ans = min(ans, temp)\n",
    "            return ans\n",
    "        return \"\".join(sorted(s))\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s) - 1):\n",
    "                s = s[1:] + s[0]\n",
    "                ans = min(ans, s)\n",
    "            return ans\n",
    "        return ''.join(sorted(s))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            m = s\n",
    "            for i in range(1, len(s)):\n",
    "                m = min(m, s[i:]+s[:i])\n",
    "            return m\n",
    "\n",
    "        s = list(s)\n",
    "        s.sort()\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k >= 2:\n",
    "            l = list(s)\n",
    "            l.sort()\n",
    "            return \"\".join(l)\n",
    "        else:\n",
    "            char = min(s)\n",
    "            indexs = []\n",
    "            next = \"z\"\n",
    "            step = 0\n",
    "            for i in range(len(s)):\n",
    "                k0 = (i + step) % (len(s))\n",
    "                k1 = (i + step + 1) % (len(s))\n",
    "\n",
    "                if s[k0] == char:\n",
    "                    indexs.append(i)\n",
    "                    if next > s[k1]:\n",
    "                        next = s[k1]\n",
    "            \n",
    "            while 1:\n",
    "                if len(indexs) == len(s):\n",
    "                    break\n",
    "                if len(indexs) <= 1:\n",
    "                    break\n",
    "                temp = []\n",
    "                temp2 = \"z\"\n",
    "                step += 1\n",
    "                for i in indexs:\n",
    "                    k0 = (i + step) % (len(s))\n",
    "                    k1 = (i + step + 1) % (len(s))\n",
    "                    if s[k0] == next:\n",
    "                        temp.append(i)\n",
    "                        if temp2 > s[k1]:\n",
    "                            temp2 = s[k1]\n",
    "\n",
    "                indexs = temp\n",
    "                next = temp2\n",
    "            i = indexs[0]\n",
    "            return s[i:] + s[:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        \"\"\"\n",
    "        1. 首先是选中那个字符，分割成三部分，字符前，字符，字符后\n",
    "        2. 三部分进行组合新字符串\n",
    "        \"\"\"\n",
    "        length = len(s)\n",
    "        if k == 1:\n",
    "            min_str = s\n",
    "            for _ in range(length):\n",
    "                s = s[1:] + s[0]\n",
    "                min_str = min(min_str, s)\n",
    "            return min_str\n",
    "        else:\n",
    "            s = sorted(list(s))\n",
    "            return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "\n",
    "        # post = s[k:]\n",
    "        # if not post:\n",
    "        #     post = []\n",
    "        # else:\n",
    "        #     post = list(post)\n",
    "        # for i in range(k):\n",
    "        #     while st and s[i] < st[-1]:\n",
    "        #         post.append(st.pop())\n",
    "            \n",
    "        #     st.append(s[i])\n",
    "        \n",
    "\n",
    "        # while st:\n",
    "\n",
    "        #     if st[-1] > s[k]:\n",
    "        #         post.append(st.pop())\n",
    "        #     elif st[-1] < s[k]:\n",
    "        #         break\n",
    "        #     else:\n",
    "\n",
    "        #         for i in range(k+1, len(s)):\n",
    "        #             if \n",
    "\n",
    "        # cccbccaccbcca, 2\n",
    "        # bccaccbccaccc\n",
    "        # baccbccaccccc\n",
    "        # if k >= 2 then we can swap any two adjcent elements thus we can reorder the entire string as we want\n",
    "        # so the answer is minimum string if k >= 2\n",
    "\n",
    "\n",
    "        if k >= 2:\n",
    "            return ''.join(sorted(list(s)))\n",
    "        \n",
    "        else:\n",
    "            ret = s\n",
    "            for i in range(1, len(s)):\n",
    "\n",
    "                cur = f'{s[i]}{s[i+1:]}{s[:i]}'\n",
    "                if ret > cur:\n",
    "                    ret = cur\n",
    "            \n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for _ in range(len(s)):\n",
    "                s = s[1:]+s[0]\n",
    "                ans = min(ans,s)        #使用min比较时，只比较第一个单词的Ascll\n",
    "            return ans\n",
    "        return ''.join(sorted(s))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k >= 2: return \"\".join(sorted(list(s)))\n",
    "        return min(s[i:] + s[:i] for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k>1:\n",
    "            return ''.join(sorted(s))\n",
    "        elif k == 1:\n",
    "            new_s = s\n",
    "            for i in range(len(s)):\n",
    "                a = s[i:]+s[:i]\n",
    "                if a<new_s:\n",
    "                    new_s = a\n",
    "            return new_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        if k > 1: return \"\".join(sorted(s))\n",
    "        n = len(s)\n",
    "        q, mini = [], \"z\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c < mini:\n",
    "                mini = c\n",
    "                q = [(i, 1, i)]\n",
    "            elif c == mini:\n",
    "                q.append((i, 1, i))\n",
    "        \n",
    "        while len(q) > 1:\n",
    "            temp, mini = [], \"z\"\n",
    "            for i, count, j in q:\n",
    "                if count == n: return (s + s)[j: j + n]\n",
    "                if s[(i + 1) % n] < mini:\n",
    "                    mini = s[(i + 1) % n]\n",
    "                    temp = [((i + 1) % n, count + 1, j)]\n",
    "                elif s[(i + 1) % n] == mini:\n",
    "                    temp.append(((i + 1) % n, count + 1, j))\n",
    "            q = temp\n",
    "        \n",
    "        j = q[0][2]\n",
    "        return (s + s)[j: j + n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderlyQueue(self, s: str, k: int) -> str:\n",
    "        n=len(s)\n",
    "        if k == 1:\n",
    "            ans = s\n",
    "            for i in range(n):\n",
    "                a = s[i:]+s[:i]\n",
    "                if a<ans:\n",
    "                    ans = a\n",
    "            return ans\n",
    "        else:\n",
    "            ans = list(s)\n",
    "            ans.sort()\n",
    "            return \"\".join(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
